This invention relates to communication control apparatuses and shaping apparatuses that may be incorporated in the communication control apparatuses.
In data communication fields, shaping method is known as a method to prevent an exclusive or excessive use of communication bands by an particular user and to ensure a fair allocation of the communication bands to a plurality of users. The shaping method may be performed by using a token bucket, as described in, for example, P. F. Chimento, “Standard Token Terminology”, May 18, 2000, retrieved from the Internet at <http://qbone.internet2.edu/bb/Traffic.pdf>.
That is, tokens are accumulated in a token bucket with a rate equivalent to a communication rate, and a length of a packet that is requested to be transmitted and stored in a queue is compared with the number of tokens accumulated in the token bucket. When the number of tokens accumulated in the token bucket is equal to or larger than a length, or a number of bytes, of the packet, the packet requested to be transmitted is allowed to transmit. Then, the number of tokens corresponding to the length of the packet allowed to be transmitted is subtracted from the tokens in the token bucket.
When a length of the packet requested to be transmitted is larger than the number of tokens in the token bucket, on the other hand, the packet is discarded or delayed until a sufficient number of tokens are accumulated in the token bucket. Accordingly, allocation of communication bands to a particular user is limited and an exclusive or excessive use of communication bands by the particular user is prevented.
When a plurality of queues is provided, it is known to provide one token bucket for each of the queues as described in, for example, Japanese Patent Publication JP 2004-336549.
Packets are stored in respective queues according to their attributions such as classes, source ports, destination ports, source addresses, destination addresses, and so on, where a plurality of queues may have some of the attributions in common. When shaping the packets in accordance with the attributions, shaping apparatuses may have token buckets for respective common attributions. The shaping apparatus compares lengths of packets stored in the queues, which are provided for storing packets having the common attribution, with the number of tokens in the token bucket and allows or refuses to transmit the packets in the queues.
FIG. 4 is a schematic drawing that shows a construction of a conventional shaping apparatus 500. The shaping apparatus 500 includes a shaping block 510 and an arbitration block 520. The shaping block 510 has a token bucked that accumulates tokens with a rate equal to a communication rate, comparators 512-515, and gates 516-519. Each of the comparators 512-515 compares a length of a packet requested to be transmitted, which is supplied from corresponding one of the queues 251-254 of the common attribution, and the number of tokens accumulated in the token bucket. The gates 516-519 allow the packets having lengths less than the number of tokens to be transmitted to the arbitration block 520.
The arbitration block 520 arbitrates the packets received through the gates 516-519 according to a predetermined policy to select one of the packets to transmit, and informs the token bucket of a length of the selected packet. The token bucket subtracts the number of tokens corresponding to the informed length of packet from the tokens in the bucket.
When transmission requests are generated for packets stored in the queues 251-254, the comparators 512-515 of the shaping apparatus 500 compare the lengths of packets requested to be transmitted and the number tokens accumulated in the token bucket 511. One or more of gates 516-519 corresponding to the comparators that detect that lengths of corresponding packets are less than the number of tokens in the token bucket open and allow corresponding packets to be transmitted to the arbitration block 520.
When two or more of the packets are allowed to be transmitted, the arbitration block 520 arbitrates the two or more of the packets and selects one of them to be transmitted, and informs the token bucket 511 of the length of the selected packet. The token bucket 511 subtracts the number of tokens corresponding to the informed length from the tokens in the token bucket. When only one of the gates 516-519 allows the corresponding packet to be transmitted to the arbitration block 520, the arbitration block 520 does not arbitrate and informs the token bucket 511 of a length of the packet.
In the shaping apparatus 500 shown in FIG. 4 where a token bucket 511 is provided for a plurality of queues 251-254, the same number of comparators 512-515 as the number of queues 251-254 are required. Moreover, signal interconnections between the token bucket 511 to each of the comparators 512-515 are required to inform the number of tokens in the token bucket 511. Signal interconnections between the queues 251-254 to corresponding comparators 512-515 are also required to inform sizes of packets stored in the queues 251-254. Accordingly, the token bucket 511 and queues 251-254 have heavy signal loads, or interconnection loads.
Furthermore, a large number of shaping apparatuses 500 are required when an available number of attributions increases. Accordingly, construction of an integrated circuit having a required number of shaping apparatuses requires an extremely large circuit area and signal loads.